
// 446.等差数列划分II
class Solution {
    typedef long long LL;
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        // 使用DP来解决 
        // 要使用一个二维DP表来实现 , dp[i][j] 其中i , j 表示最后两个位置的元素下标
        int n = nums.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        unordered_map<LL,vector<LL>> m;
        m[nums[0]].push_back(0);
        int ret = 0;
        for(int i = 1; i < n; i++)              // 枚举倒数第二个数
        {
            for(int j = i + 1 ; j < n ; j++)    // 枚举倒数第一个数
            {
                LL a = 2 * (LL)nums[i] - nums[j] ;
                if(m.count(a))
                {
                    for(auto& index : m[a])
                        dp[i][j] += dp[index][i] + 1;
                }
                ret += dp[i][j]; 
            }
            m[nums[i]].push_back(i);
        }
        return ret;
    }

};